from typing import List


# 暴力法
class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        if len(nums) < 2:
            return sum(nums)
        max_sum = max(nums)
        for i in range(len(nums)-1):
            for j in range(i, len(nums)):
                max_sum = max(max_sum, sum(nums[i:j+1]))
        return max_sum


# 动态规划
class Solution1:
    def maxSubArray(self, nums: List[int]) -> int:
        if len(nums) < 2:
            return sum(nums)
        for i in range(1, len(nums)):
            if nums[i-1] > 0:
                nums[i] += nums[i-1]
        return max(nums)


class Solution2:
    def maxSubArray(self, nums: List[int]):
        if len(nums) < 2:
            return nums
        i, j = 0, 1
        dp = [x for x in nums]
        temp_nums = [nums[0]]
        max_sum = nums[0]
        for idx in range(1, len(dp)):
            if dp[idx-1] > 0:
                dp[idx] += dp[idx-1]
                if dp[idx] > max_sum:
                    max_sum = dp[idx]
                j = idx + 1
            else:
                if dp[idx] >= max_sum:
                    i, j = idx, idx+1
            if sum(nums[i:j]) > sum(temp_nums):
                temp_nums = nums[i: j]
        return temp_nums


if __name__ == '__main__':
    x = Solution2()
    t = [4,-2,1,3,-10,4,-1,2,2,-5,4]
    print(x.maxSubArray(t))